package com.springboot.test.sort;

import java.util.Arrays;

/**
 *  希尔排序  插入排序的升级，由于插入排序在数量量非常大时 效率底下 所以
 *      记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，
 *      每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
 */
public class ShellSort {

    public static void main(String[] args) {

        int[] arr = {12, 9, 6, 11, 5, 1, 14, 2, 10, 4, 8, 7, 13, 3};

        System.out.println(Arrays.toString(arr));
        // 分组
        for(int gap=arr.length/2;gap > 0; gap=gap/2){
            // 当前增量下所有分组
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                // 分组内插入排序 从左向右依次对比
                while (j -gap >= 0 && arr[j] < arr[j-gap]){
                    swap(arr, j, j-gap);
                    j -= gap;
                }
            }
        }

        System.out.println(Arrays.toString(arr));
    }

    public static void swap(int[] arr, int i, int max_idx){
        int tmp = arr[i];
        arr[i] = arr[max_idx];
        arr[max_idx] = tmp;
    }
}
